package com.company.zoj;

import com.company.Sort.QuickSort;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/**
 * Created by v on 17-6-22.
 */
public class ZojTest1788 {
    private static int[][] map;
    private static int n;
    private static int m;

    private static Stack<Character> stack;

    private static Node root;

    private static StringBuffer buffer;

    private static class Node{
        String str;
        Node[] child;
    }

    private static void change(StringBuffer str){
        for(int i=str.length()-1;i>=0;){
            int temp=0;
            int a=1;
            for(int j=0;j<4&&i>=0;j++,i--){
                temp=temp+(str.charAt(i)-'0')*a;
                a*=2;
            }
            stack.push(Integer.toHexString(temp).toUpperCase().charAt(0));
        }
    }

    //遍历
    private static void solve(){
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            Node node=queue.poll();
            buffer.append(node.str);

            if(node.child!=null){
                for(int i=0;i<node.child.length;i++){
                    queue.offer(node.child[i]);
                }
            }
        }

    }

    private static Node build(int x1,int y1,int x2,int y2){
        Node node=new Node();

        if(x1!=x2){
            node.child=new Node[4];
            node.child[0]=build(x1,y1,(x1+x2)/2,(y1+y2)/2);
            node.child[1]=build(x1,(y1+y2)/2+1,(x1+x2)/2,y2);
            node.child[2]=build((x1+x2)/2+1,y1,x2,(y1+y2)/2);
            node.child[3]=build((x1+x2)/2+1,(y1+y2)/2+1,x2,y2);
        }else {
            node.str="0"+map[x1][y1];
            return node;
        }

        if(all(node)&&node.child[0].str.charAt(0)=='0'){
            node.str="0"+node.child[0].str.charAt(1);
            node.child=null;
        }else {
            node.str="1";
        }

        return node;
    }

    private static boolean all(Node node){
        String str=node.child[0].str;
        for(int i=1;i<4;i++){
            if(!str.equals(node.child[i].str)){
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);

        n=input.nextInt();
        for(int i=0;i<n;i++){
            stack=new Stack<>();
            m=input.nextInt();
            map=new int[m][m];
            buffer=new StringBuffer();
            for(int j=0;j<m;j++){
                for(int k=0;k<m;k++){
                    map[j][k]=input.nextInt();
                }
            }

            root=build(0,0,m-1,m-1);
            solve();
            change(buffer);

            while (!stack.empty()){
                System.out.print(stack.pop());
            }
            System.out.println();
        }
    }
}
